package practice1_100;

import com.sun.source.tree.Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Practice105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer,Integer> map =new HashMap<>();
        for (int i=0;i<preorder.length;i++){
            map.put(inorder[i],i);
        }
           TreeNode root= dp(preorder,inorder,0,preorder.length-1,0,preorder.length-1,map);
           return root;
    }

    public TreeNode dp(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd, Map map){
       //条件判断
        if(inStart>inEnd||preStart>=preEnd) return null;//


        TreeNode root=new TreeNode(preorder[preStart]);
//        int premid,inmid=0;
//        for (int i=inStart;i<=inEnd;i++){
//            if(inorder[i]==preorder[preStart]){
//               inmid=i;
//               break;
//            }
//        }
       int inmid = (int) map.get(preorder[preStart]);

        root.left =dp(preorder,inorder,preStart+1,preStart+inmid-inStart,inStart,inmid-1,map);
        root.right =dp(preorder,inorder,preStart+inmid-inStart+1,preEnd,inmid+1,inEnd,map);

        return root;
    }

    public static void main(String[] args) {
        TreeNode a= new Practice105().buildTree(new int[]{1,2,3},new int[] {2,3,1});
        System.out.println(a);
    }
}
